home *** CD-ROM | disk | FTP | other *** search
/ GameStar 2004 April / Gamestar_61_2004-04_dvdb.iso / DVDStar / Editace / hltp.exe / {app} / Source Code / Zoners Half-Life Tools / hlbsp / surfaces.cpp < prev    next >
C/C++ Source or Header  |  2002-11-16  |  8KB  |  306 lines
  1. #include "bsp5.h"
  2.  
  3. //  SubdivideFace
  4.  
  5. //  InitHash
  6. //  HashVec
  7.  
  8. //  GetVertex
  9. //  GetEdge
  10. //  MakeFaceEdges
  11.  
  12. static int      subdivides;
  13.  
  14. /* a surface has all of the faces that could be drawn on a given plane
  15.    the outside filling stage can remove some of them so a better bsp can be generated */
  16.  
  17. // =====================================================================================
  18. //  SubdivideFace
  19. //      If the face is >256 in either texture direction, carve a valid sized
  20. //      piece off and insert the remainder in the next link
  21. // =====================================================================================
  22. void            SubdivideFace(face_t* f, face_t** prevptr)
  23. {
  24.     vec_t           mins, maxs;
  25.     vec_t           v;
  26.     int             axis;
  27.     int             i;
  28.     dplane_t        plane;
  29.     face_t*         front;
  30.     face_t*         back;
  31.     face_t*         next;
  32.     texinfo_t*      tex;
  33.     vec3_t          temp;
  34.  
  35.     // special (non-surface cached) faces don't need subdivision
  36.  
  37.     tex = &g_texinfo[f->texturenum];
  38.  
  39.     if (tex->flags & TEX_SPECIAL) 
  40.     {
  41.         return;
  42.     }
  43.  
  44.     if (f->facestyle == face_hint)
  45.     {
  46.         return;
  47.     }
  48.     if (f->facestyle == face_skip)
  49.     {
  50.         return;
  51.     }
  52.  
  53. #ifdef ZHLT_NULLTEX    // AJM
  54.     if (f->facestyle == face_null)
  55.         return; // ideally these should have their tex_special flag set, so its here jic
  56. #endif
  57.  
  58.     for (axis = 0; axis < 2; axis++)
  59.     {
  60.         while (1)
  61.         {
  62.             mins = 999999;
  63.             maxs = -999999;
  64.  
  65.             for (i = 0; i < f->numpoints; i++)
  66.             {
  67.                 v = DotProduct(f->pts[i], tex->vecs[axis]);
  68.                 if (v < mins)
  69.                 {
  70.                     mins = v;
  71.                 }
  72.                 if (v > maxs)
  73.                 {
  74.                     maxs = v;
  75.                 }
  76.             }
  77.  
  78.             if ((maxs - mins) <= g_subdivide_size)
  79.             {
  80.                 break;
  81.             }
  82.                 
  83.             // split it
  84.             subdivides++;
  85.  
  86.             VectorCopy(tex->vecs[axis], temp);
  87.             v = VectorNormalize(temp);
  88.  
  89.             VectorCopy(temp, plane.normal);
  90.             plane.dist = (mins + g_subdivide_size - 16) / v;
  91.             next = f->next;
  92.             SplitFace(f, &plane, &front, &back);
  93.             if (!front || !back)
  94.             {
  95.                 Developer(DEVELOPER_LEVEL_SPAM, "SubdivideFace: didn't split the %d-sided polygon @(%.0f,%.0f,%.0f)",
  96.                         f->numpoints, f->pts[0][0], f->pts[0][1], f->pts[0][2]);
  97.                 break;
  98.             }
  99.             *prevptr = back;
  100.             back->next = front;
  101.             front->next = next;
  102.             f = back;
  103.         }
  104.     }
  105. }
  106.  
  107. //===========================================================================
  108.  
  109. typedef struct hashvert_s
  110. {
  111.     struct hashvert_s* next;
  112.     vec3_t          point;
  113.     int             num;
  114.     int             numplanes;                             // for corner determination
  115.     int             planenums[2];
  116.     int             numedges;
  117. }
  118. hashvert_t;
  119.  
  120. // #define      POINT_EPSILON   0.01
  121. #define POINT_EPSILON    ON_EPSILON
  122.  
  123. static hashvert_t hvertex[MAX_MAP_VERTS];
  124. static hashvert_t* hvert_p;
  125.  
  126. static face_t*  edgefaces[MAX_MAP_EDGES][2];
  127. static int      firstmodeledge = 1;
  128. static int      firstmodelface;
  129.  
  130. //============================================================================
  131.  
  132. #define    NUM_HASH    4096
  133.  
  134. static hashvert_t* hashverts[NUM_HASH];
  135.  
  136. static vec3_t   hash_min;
  137. static vec3_t   hash_scale;
  138.  
  139. // =====================================================================================
  140. //  InitHash
  141. // =====================================================================================
  142. static void     InitHash()
  143. {
  144.     vec3_t          size;
  145.     vec_t           volume;
  146.     vec_t           scale;
  147.     int             newsize[2];
  148.     int             i;
  149.  
  150.     memset(hashverts, 0, sizeof(hashverts));
  151.  
  152.     for (i = 0; i < 3; i++)
  153.     {
  154.         hash_min[i] = -8000;
  155.         size[i] = 16000;
  156.     }
  157.  
  158.     volume = size[0] * size[1];
  159.  
  160.     scale = sqrt(volume / NUM_HASH);
  161.  
  162.     newsize[0] = size[0] / scale;
  163.     newsize[1] = size[1] / scale;
  164.  
  165.     hash_scale[0] = newsize[0] / size[0];
  166.     hash_scale[1] = newsize[1] / size[1];
  167.     hash_scale[2] = newsize[1];
  168.  
  169.     hvert_p = hvertex;
  170. }
  171.  
  172. // =====================================================================================
  173. //  HashVec
  174. // =====================================================================================
  175. static unsigned HashVec(const vec3_t vec)
  176. {
  177.     unsigned        h;
  178.  
  179.     h = hash_scale[0] * (vec[0] - hash_min[0]) * hash_scale[2] + hash_scale[1] * (vec[1] - hash_min[1]);
  180.     if (h >= NUM_HASH)
  181.     {
  182.         return NUM_HASH - 1;
  183.     }
  184.     return h;
  185. }
  186.  
  187. // =====================================================================================
  188. //  GetVertex
  189. // =====================================================================================
  190. static int      GetVertex(const vec3_t in, const int planenum)
  191. {
  192.     int             h;
  193.     int             i;
  194.     hashvert_t*     hv;
  195.     vec3_t          vert;
  196.  
  197.     for (i = 0; i < 3; i++)
  198.     {
  199.         if (fabs(in[i] - VectorRound(in[i])) < 0.001)
  200.         {
  201.             vert[i] = VectorRound(in[i]);
  202.         }
  203.         else
  204.         {
  205.             vert[i] = in[i];
  206.         }
  207.     }
  208.  
  209.     h = HashVec(vert);
  210.  
  211.     for (hv = hashverts[h]; hv; hv = hv->next)
  212.     {
  213.         if (fabs(hv->point[0] - vert[0]) < POINT_EPSILON
  214.             && fabs(hv->point[1] - vert[1]) < POINT_EPSILON && fabs(hv->point[2] - vert[2]) < POINT_EPSILON)
  215.         {
  216.             hv->numedges++;
  217.             if (hv->numplanes == 3)
  218.             {
  219.                 return hv->num;                            // allready known to be a corner
  220.             }
  221.             for (i = 0; i < hv->numplanes; i++)
  222.             {
  223.                 if (hv->planenums[i] == planenum)
  224.                 {
  225.                     return hv->num;                        // allready know this plane
  226.                 }
  227.             }
  228.             if (hv->numplanes != 2)
  229.             {
  230.                 hv->planenums[hv->numplanes] = planenum;
  231.             }
  232.             hv->numplanes++;
  233.             return hv->num;
  234.         }
  235.     }
  236.  
  237.     hv = hvert_p;
  238.     hv->numedges = 1;
  239.     hv->numplanes = 1;
  240.     hv->planenums[0] = planenum;
  241.     hv->next = hashverts[h];
  242.     hashverts[h] = hv;
  243.     VectorCopy(vert, hv->point);
  244.     hv->num = g_numvertexes;
  245.     hlassume(hv->num != MAX_MAP_VERTS, assume_MAX_MAP_VERTS);
  246.     hvert_p++;
  247.  
  248.     // emit a vertex
  249.     hlassume(g_numvertexes < MAX_MAP_VERTS, assume_MAX_MAP_VERTS);
  250.  
  251.     g_dvertexes[g_numvertexes].point[0] = vert[0];
  252.     g_dvertexes[g_numvertexes].point[1] = vert[1];
  253.     g_dvertexes[g_numvertexes].point[2] = vert[2];
  254.     g_numvertexes++;
  255.  
  256.     return hv->num;
  257. }
  258.  
  259. //===========================================================================
  260.  
  261. // =====================================================================================
  262. //  GetEdge
  263. //      Don't allow four way edges
  264. // =====================================================================================
  265. int             GetEdge(const vec3_t p1, const vec3_t p2, face_t* f)
  266. {
  267.     int             v1;
  268.     int             v2;
  269.     dedge_t*        edge;
  270.     int             i;
  271.  
  272.     hlassert(f->contents);
  273.  
  274.     v1 = GetVertex(p1, f->planenum);
  275.     v2 = GetVertex(p2, f->planenum);
  276.     for (i = firstmodeledge; i < g_numedges; i++)
  277.     {
  278.         edge = &g_dedges[i];
  279.         if (v1 == edge->v[1] && v2 == edge->v[0] && !edgefaces[i][1] && edgefaces[i][0]->contents == f->contents)
  280.         {
  281.             edgefaces[i][1] = f;
  282.             return -i;
  283.         }
  284.     }
  285.  
  286.     // emit an edge
  287.     hlassume(g_numedges < MAX_MAP_EDGES, assume_MAX_MAP_EDGES);
  288.     edge = &g_dedges[g_numedges];
  289.     g_numedges++;
  290.     edge->v[0] = v1;
  291.     edge->v[1] = v2;
  292.     edgefaces[i][0] = f;
  293.  
  294.     return i;
  295. }
  296.  
  297. // =====================================================================================
  298. //  MakeFaceEdges
  299. // =====================================================================================
  300. void            MakeFaceEdges()
  301. {
  302.     InitHash();
  303.     firstmodeledge = g_numedges;
  304.     firstmodelface = g_numfaces;
  305. }
  306.